This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

The following problem is considered: Given a rectilinear simple polygon P and a point q in its exterior, find the region that is reachable from q along orthogonal paths with at most k bends. For this problem we preset an efficient algorithm which runs in O(kn) time, where n is the number of vertices.

Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great number of algorithms have been presented for this problem, some of which have only been evaluated just by comparison with human eyes. In this paper we formulate the digital halftoning problem as a combinatiorial problem which allows an exact solution with graph-theoretic tools. For this, we consider a d-dimensional grid of n := Nd pixels (d 1). For each pixel, we define a so-called k-neighborhood, k {0,...N - 1}, which is the set of at most (2k + 1)d pixels that can be reached from the current pixel in a distance of k. Now, in order to solve the digital halftoning problem, we are going to minimize the sum of distances of all k-neighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the one-dimensional case while it looks hopeless to have a polynomial-time algorithm in higher dimension including the usual two-dimensional case. We present an exact algorithm for the one-dimensional case which runs in O(n) time if k is regarded to be a constant. For two-dimensional case we present fast approximation techniques based on space filling curves. An experimental comparison of several implementations of approximate algorithms proves that our algorithms are of practical interest.

Among the most fundamental problems in the layout design of an integrated circuit is the following problem: Given a region bounded by n orthogonal line segments and a point q in its interior, find the region that is reachable from q along rectilinear paths with at most k bends which avoid obstructions, where k is some given constant. In this paper we present an efficient algorithm which determines such a region in O(kn) time for a rectilinear simple polygon without any hole in it.